package _18_剑指OfferII;

import _18_剑指OfferII.datastrcute.Nodes;

public class _028_剑指OfferII展平多级双向链表 {

    public Nodes flatten(Nodes head) {
        dfs(head);
        return head;
    }

    private Nodes dfs(Nodes head) {
        Nodes prev = null;
        while (head != null) {
            prev = head;
            Nodes next = head.next;
            if (head.child != null) {
                Nodes tailNode = dfs(head.child);
                head.next = head.child;
                head.child.prev = head;
                head.child = null;
                if (next != null) {
                    tailNode.next = next;
                    next.prev = tailNode;
                }
                // 上一个节点替换成尾节点
                prev = tailNode;
            }
            head = next;
        }
        return prev;
    }

}
